/*
 * @lc app=leetcode.cn id=221 lang=golang
 *
 * [221] 最大正方形
 */

// @lc code=start

func maximalSquare(matrix [][]byte) int {
	m, n := len(matrix), len(matrix[0])
	//dp[i][j]表示以i、j为右下角端点的最大正方形的边长
	dp := make([]int, n+1)
	l := 0
	for i := 0; i < m; i++ {
		tmp := make([]int, n+1)
		for j := 0; j < n; j++ {
			if matrix[i][j] != '0' {
				tmp[j+1] = min(dp[j], min(dp[j+1], tmp[j])) + 1
			}
			l = max(tmp[j+1], l)
		}

		dp = tmp
	}
	// for i,_:=range dp{
	// 	dp[i] = make([][])
	// }
	return l * l
}
func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}
func min(i, j int) int {
	if i < j {
		return i
	}
	return j
}

// @lc code=end
